# -*- coding=utf-8 -*-
# 编写一个程序，通过已填充的空格来解决数独问题

# 一个数独的解法需遵循如下规则：
# 数字 1-9 在每一行只能出现一次
# 数字 1-9 在每一列只能出现一次
# 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次

# Note:
# 给定的数独序列只包含数字 1-9 和字符 '.'
# 你可以假设给定的数独只有唯一解
# 给定数独永远是 9x9 形式的

class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        self.possible_row = [set() for i in range(9)];
        self.possible_col = [set() for i in range(9)];
        self.possible_box = [set() for i in range(9)];

        for row in range(9):
            for col in range(9):
                if board[row][col] == ".":
                    continue;

                index = (row / 3) * 3 + col / 3;
                value = board[row][col];
                self.possible_row[row].add(value);
                self.possible_col[col].add(value);
                self.possible_box[index].add(value);

        for index in range(9):
            self.possible_row[index] = set(['1','2','3','4','5','6','7','8','9']) - self.possible_row[index];
            self.possible_col[index] = set(['1','2','3','4','5','6','7','8','9']) - self.possible_col[index];
            self.possible_box[index] = set(['1','2','3','4','5','6','7','8','9']) - self.possible_box[index];

        # self.print_board(board);
        self.deduce(board);
        # self.print_board(board);
        self.recursive(board);
        # self.print_board(board);

    def recursive(self, board):
        index = self.next_unknow_index(board);
        if index == None:
            return True;

        possibles = self.possible(index[0], index[1]);
        if not possibles:
            # print "FAIL";
            return False;

        for value in possibles:
            self.set_board(board, index[0], index[1], value);
            # print [index, possibles, value];
            self.print_board(board);
            if not self.recursive(board):
                self.back_board(board, index[0], index[1], value);
            else:
                return True;


    # 根据集合推断所在位置的数值
    def deduce(self, board):
        unknown_count = self.unknown_num(board);
        if unknown_count == 0:
            return;

        unknown_count_before = unknown_count;
        unknown_count_after = -1;

        while unknown_count_after != 0 and unknown_count_after != unknown_count_before:
            unknown_count_before = unknown_count_after;

            for row in range(9):
                for col in range(9):
                    if board[row][col] != ".":
                        continue;

                    possible_row_col = self.possible(row, col);
                    if len(possible_row_col) == 1:
                        self.set_board(board, row, col, possible_row_col[0]);
                    else:
                        possible_in_box = self.possible_in_box(board, row, col);
                        if len(possible_in_box) == 1:
                            self.set_board(board, row, col, possible_in_box[0]);

            unknown_count_after = self.unknown_num(board);

    # 未知元素的个数
    def unknown_num(self, board):
        count = 0;
        for i in xrange(9):
            for j in xrange(9):
                if board[i][j] != ".":
                    continue;
                count += 1;
        return count;

    # 根据行、列、九宫找出各个位置的可能数值
    def possible(self, row, col):
        index = (row / 3) * 3 + col / 3;
        sss = self.possible_row[row] & self.possible_col[col] & self.possible_box[index];
        return [item for item in sss];

    # 九宫中别人都没有，那就只能是自己有了
    def possible_in_box(self, board, row, col):
        index = (row / 3) * 3 + col / 3;

        box_possible_set = set();
        for i in range(3):
            for j in range(3):
                box_row = index / 3 * 3 + i;
                box_col = index % 3 * 3 + j;
                if row == box_row and col == box_col:
                    continue;

                if board[box_row][box_col] != ".":
                    box_possible_set.add(board[box_row][box_col]);
                    continue;

                box_possible_set = box_possible_set | (self.possible_row[box_row] & self.possible_col[box_col] & self.possible_box[index]);

        sss = set(['1','2','3','4','5','6','7','8','9']) - box_possible_set;
        return [item for item in sss];

    # 设置board的数值
    def set_board(self, board, row, col, value):
        index = (row / 3) * 3 + col / 3;
        board[row][col] = value;

        self.possible_row[row].remove(value);
        self.possible_col[col].remove(value);
        self.possible_box[index].remove(value);

    # 恢复board的数值
    def back_board(self, board, row, col, value):
        index = (row / 3) * 3 + col / 3;
        board[row][col] = ".";

        self.possible_row[row].add(value);
        self.possible_col[col].add(value);
        self.possible_box[index].add(value);

    # 下一个未知元素的位置
    def next_unknow_index(self, board):
        for i in xrange(9):
            for j in xrange(9):
                if board[i][j] != ".":
                    continue;
                return [i, j];
        return None;

    def print_board(self, board):
        print "-" * 45;
        for row in xrange(9):
            if row % 3 == 0:
                print "#" * 45;
            print board[row];
        print "-" * 45;

t = Solution();
# print t.solveSudoku(
# [
#     ["5","3",".",".","7",".",".",".","."],
#     ["6",".",".","1","9","5",".",".","."],
#     [".","9","8",".",".",".",".","6","."],
#     ["8",".",".",".","6",".",".",".","3"],
#     ["4",".",".","8",".","3",".",".","1"],
#     ["7",".",".",".","2",".",".",".","6"],
#     [".","6",".",".",".",".","2","8","."],
#     [".",".",".","4","1","9",".",".","5"],
#     [".",".",".",".","8",".",".","7","9"]
# ]);

print t.solveSudoku(
[
    [".",".","9","7","4","8",".",".","."],
    ["7",".",".",".",".",".",".",".","."],
    [".","2",".","1",".","9",".",".","."],
    [".",".","7",".",".",".","2","4","."],
    [".","6","4",".","1",".","5","9","."],
    [".","9","8",".",".",".","3",".","."],
    [".",".",".","8",".","3",".","2","."],
    [".",".",".",".",".",".",".",".","6"],
    [".",".",".","2","7","5","9",".","."]
]);

# [
#     ["5","1","9","7","4","8","6","3","2"],
#     ["7","8","3","6","5","2","4","1","9"],
#     ["4","2","6","1","3","9","8","7","5"],

#     ["3","5","7","9","8","6","2","4","1"],
#     ["2","6","4","3","1","7","5","9","8"],
#     ["1","9","8","5","2","4","3","6","7"],

#     ["9","7","5","8","6","3","1","2","4"],
#     ["8","3","2","4","9","1","7","5","6"],
#     ["6","4","1","2","7","5","9","8","3"]
# ]